﻿

namespace Graph.Algorithm.Core;

public class DijkstraService
{

    List<Record> _records = new List<Record>();

    public IList<Record> RunAlgm(int stIndex, IEnumerable<GraphEdge> edges)
    {
        PriorityQueue<int, double> queue = new PriorityQueue<int, double>(Comparer<double>.Create((a, b) => Math.Sign(a - b)));

        //GenRecord
        List<Record> records = new List<Record>();
        records = edges
            .GroupBy(e => e.stVertexId)
            .Select(g => g.First())
            .Select(e => new Record() { id = e.stVertexId })
            .ToList();
        //records = vertexs.Select(v => new Record() { id = v.id }).ToList();

        //ready 
        {
            var stRec = records.Where(r => r.id == stIndex).First();
            stRec.dist = 0;
            queue.Enqueue(stIndex, 0d);
        }

        //start
        int maxCount = 10000;
        while (maxCount > 0)
        {
            //IF BREAK
            maxCount--;
            if (queue.Count == 0) break;

            //临时起点
            var tmpIndex = queue.Dequeue();
            var tmpEdges = edges.AtSt(tmpIndex); // edges.Where(e => e.stVertexId == tmpIndex).ToList();
            var parentDist = records.Where(r => r.id == tmpIndex).First().dist;

            //
            foreach (var tmpEdge in tmpEdges)
            {
                int focusId = tmpEdge.edVertexId;
                var curRec = records.Where(r => r.id == focusId).First();
                double newDist = parentDist + Math.Max(0, tmpEdge.weight); //权重必须非负  否则一直迭代
                if (newDist < curRec.dist)
                {
                    curRec.dist = newDist;
                    curRec.parentId = tmpEdge.stVertexId;
                    queue.Enqueue(focusId, newDist);
                }
            }
        }
        _records = records;
        return records;
    }

    public IList<int> GetPathIds(int stIndex, int edIndex)
    {
        List<int> ids = new List<int>();

        var records = _records;
        ids.Add(edIndex);
        int count = records.Count + 3;
        while (count > 0)
        {
            count--;

            var edRecord = records.Where(r => r.id == edIndex).First();
            ids.Add(edRecord.parentId);
            if (stIndex == edRecord.parentId) { break; }
        }
        return ids;
    }

    public struct Record
    {
        public Record()
        {
            this.id = 0;
            this.dist = double.MaxValue;
            this.parentId = 0;
        }
        public int id { get; set; }
        public double dist { get; set; }
        public int parentId { get; set; }

    }



}